|
A counter machine is an abstract machine used in formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines. A counter machine comprises a set of one or more unbounded ''registers'', each of which can hold a single non-negative integer, and a list of (usually sequential) arithmetic and control instructions for the machine to follow. == Basic features == For a given counter machine model the instruction set is tiny—from just one to six or seven instructions. Most models contain a few arithmetic operations and at least one conditional operation (if ''condition'' is true, then jump). Three ''base models'', each using three instructions, are drawn from the following collection. (The abbreviations are arbitrary.) * CLR (r): CLeaR register ''r''. (Set ''r'' to zero.) * INC (r): INCrement the contents of register ''r''. * DEC (r): DECrement the contents of register ''r''. * CPY (rj, rk): CoPY the contents of register ''rj'' to register ''rk'' leaving the contents of ''rj'' intact. * JZ (r, z): IF register ''r'' contains Zero THEN Jump to instruction ''z'' ELSE continue in sequence. * JE (rj, rk, z): IF the contents of register ''rj'' Equals the contents of register ''rk'' THEN Jump to instruction ''z'' ELSE continue in sequence. In addition, a machine usually has a HALT instruction, which stops the machine (normally after the result has been computed). Using the instructions mentioned above, various authors have discussed certain counter machines: * set 1: , (Minsky (1961, 1967), Lambek (1961)) * set 2: , (Ershov (1958), Peter (1958) as interpreted by Shepherdson-Sturgis (1964); Minsky (1967); Schönhage (1980)) * set 3: , (Elgot-Robinson (1964), Minsky (1967)) The three counter machine base models have the same computational power since the instructions of one model can be derived from those of another. All are equivalent to the computational power of Turing machines (but only if Gödel numbers are used to encode data in the register or registers; otherwise their power is equivalent to the primitive recursive functions). Due to their unary processing style, counter machines are typically exponentially slower than comparable Turing machines. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「counter machine」の詳細全文を読む スポンサード リンク
|